use std::ops::Deref;

#[derive(Clone,Copy,Debug)]
pub struct DataField<T> {
    data:T,
    prev:usize,
    next:usize,
}

#[derive(Clone,Copy,Debug)]
struct NoneField {
    prev:usize,
    next:usize,
}

#[derive(Clone,Copy,Debug)]
enum LruXcacheNode<T> {
    None(NoneField),
    Some(DataField<T>),
}

impl<T> LruXcacheNode<T> {
    fn next(&self) -> usize {
        match self {
            Self::Some(d) => d.next,
            Self::None(n) => n.next,
        }
    }

    fn prev(&self) -> usize {
        match self {
            Self::Some(d) => d.prev,
            Self::None(n) => n.prev,
        }
    }

    fn set_next(&mut self,next:usize) {
        match self {
            Self::Some(d) => d.next = next,
            Self::None(n) => n.next = next,
        }
    }

    fn set_prev(&mut self,prev:usize) {
        match self {
            Self::Some(d) => d.prev = prev,
            Self::None(n) => n.prev = prev,
        }
    }

    fn data_unwrap(&self) -> &DataField<T> {
        match self {
            Self::Some(d) => d,
            Self::None(_) => panic!("it is not a data field"),
        }
    }
}

impl<T> Deref for DataField<T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        &self.data
    }
}

#[derive(Debug)]
pub struct LruXcache<T>{
    cap:usize,
    list:Vec<LruXcacheNode<T>>,
}

impl<T> LruXcache<T> {
    pub fn with_capacity(cap:usize) -> Self {
        assert!(cap > 1);
        Self {
            cap:cap,
            list:{
                let mut list = Vec::with_capacity(cap+1);
                list.push(LruXcacheNode::None(NoneField { prev: 0, next: 0 }));
                list
            }
        }
    }

    fn set_max_priority(&mut self,node_no:usize) {
        let cur_node = &self.list[node_no];
        let origin_prev = cur_node.prev();
        let origin_next = cur_node.next();
        self.list[origin_prev].set_next(origin_next);
        self.list[origin_next].set_prev(origin_prev);
        let new_prev = 0;
        let new_next = self.list[0].next();
        self.list[new_prev].set_next(node_no);
        self.list[new_next].set_prev(node_no);
        self.list[node_no].set_next(new_next);
        self.list[node_no].set_prev(new_prev);
    }

    pub(crate) fn get(&self,no:usize) -> &DataField<T> {
        self.list[no].data_unwrap()
    }

    pub fn insert(&mut self,t:T) -> usize {
        let list_len = self.list.len();
        if list_len < self.cap + 1 {
            let prev = 0;
            let next = self.list[0].next();
            self.list[0].set_next(list_len);
            self.list[next].set_prev(list_len);
            self.list.push(LruXcacheNode::Some(DataField { data: t, prev: prev, next: next }));
            list_len
        } else {
            let tail = self.list[0].prev();
            self.set_max_priority(tail);
            match &mut self.list[tail] {
                LruXcacheNode::Some(data_field) => data_field.data = t,
                LruXcacheNode::None(_) => unreachable!(),
            }
            tail
        }
    }

    pub fn insert_with_drop<F:FnMut(&T)>(&mut self,t:T,mut local_drop:F) -> usize {
        let list_len = self.list.len();
        if list_len < self.cap + 1 {
            let prev = 0;
            let next = self.list[0].next();
            self.list[0].set_next(list_len);
            self.list[next].set_prev(list_len);
            self.list.push(LruXcacheNode::Some(DataField { data: t, prev: prev, next: next }));
            list_len
        } else {
            let tail = self.list[0].prev();
            self.set_max_priority(tail);
            match &mut self.list[tail] {
                LruXcacheNode::Some(data_field) => {
                    local_drop(&data_field.data);
                    data_field.data = t;
                }
                LruXcacheNode::None(_) => unreachable!(),
            }
            tail
        }
    }

    pub fn insert_node(&mut self,node:DataField<T>) {
        let cur = self.list[node.next].prev();
        self.set_max_priority(cur);
    }

    pub fn iter(&self) -> impl std::iter::Iterator + '_ {
        self.list.iter().filter_map(|node|match node {
            LruXcacheNode::Some(data_filed) => Some(data_filed),
            LruXcacheNode::None(_) => None,
        })
    }
}